package leetcode.weekly.week306;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int countSpecialNumbers(int n) {
		int[] f = new int[11];
		f[1] = 9;
		for (int i = 2, j = 9; i < f.length; i++) {
			f[i] = f[i - 1] * j--;
		}
		int[] ff = new int[11];
		for (int i = 1; i < ff.length; i++) {
			ff[i] = ff[i - 1] + f[i];
		}
		int[][] follows = new int[11][10];
		Arrays.fill(follows[0], 1);
		follows[1][0] = 9;// 1位，缺0个，后续
		for (int i = 1; i < 10; i++) {
			follows[1][i] = follows[1][i - 1] - 1;
		}
		for (int i = 0; i < follows[0].length; i++) {
			for (int j = 2, k = follows[1][i] - 1; j < follows.length; j++) {
				follows[j][i] = follows[j - 1][i] * k--;
			}
		}
		H.print(follows);
		int len = 0, num = n;
		while (num > 0) {
			len++;
			num /= 10;
		}
		int[] nums = new int[len + 1];
		num = n;
		int p = len;
		while (num > 0) {
			nums[p--] = num % 10;
			num /= 10;
		}
		int ans = ff[len - 1];
		// 56732;
		ans += (nums[1] - 1) * follows[len - 1][1];
		Set<Integer> set = new HashSet<>();
		set.add(nums[1]);
		for (int i = 2; i < nums.length; i++) {
			int cur = nums[i];
			int cnt = 0;
			for (int j = 0; j < cur; j++) {
				if (!set.contains(j)) {
					cnt++;
				}
			}
			ans += cnt * follows[len - i][i];
			set.add(cur);
		}
		return ans;
	}

//	H.printObject(start);
//	H.printObject(follow);
//	System.out.println(f[3]);
//	System.out.println(ff[3]);
//	H.printObject(f);
//	H.printObject(ff);

//	int[] start = new int[11];
//	start[0] = 9;
//	for (int i = 1; i < start.length; i++) {
//		start[i] = start[i - 1] - 1;
//	}
//	int[] follow = new int[11];
//	follow[0] = 10;
//	for (int i = 1; i < follow.length; i++) {
//		follow[i] = follow[i - 1] - 1;
//	}
//	H.printObject(follow);
	@Override
	public void debug4() {
		H.compare(110, this.countSpecialNumbers(99));
//		H.compare(19281, this.countSpecialNumbers(56732));
//		H.compare(738, this.countSpecialNumbers(999));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		int num = 0b1101101;
		System.out.println(num);
		System.out.println(Integer.toBinaryString(num));
		System.out.println(Integer.toBinaryString(~num));
		System.out.println(Integer.toBinaryString(num & ~num));
	}

}
